package previous.Test_0317;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> hash=new HashSet<>();
        for (String s:wordList) {
            hash.add(s);
        }
        Set<String> vis=new HashSet<>();
        if(!hash.contains(endWord)) return 0;
        Queue<String> q=new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        int ret=1;
        while(!q.isEmpty()){
            int sz=q.size();
            ret++;
            for (int i = 0; i < sz; i++) {
                String t=q.poll();
                for (int j = 0; j < t.length(); j++) {
                    char[] tmp=t.toCharArray();
                    for (char k = 'a'; k <='z' ; k++) {
                        tmp[j]=k;
                        String n=new String(tmp);
                        if(hash.contains(n) && !vis.contains(n)){
                            q.add(n);
                            vis.add(n);
                            if(n.equals(endWord)) return ret;
                        }
                    }
                }
            }
        }
        return -1;
        }
        //为高尔夫比赛砍树
    int m;
    int n;
    public int cutOffTree(List<List<Integer>> forest) {
        //找到大于0的下标并存储
        List<int[]> trees=new ArrayList<>();
         m=forest.size();
         n=forest.get(0).size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(forest.get(i).get(j)>1){
                    trees.add(new int[]{i,j});
                }
            }
        }
        Collections.sort(trees,(a,b) ->
        {
            return forest.get(a[0]).get(a[1])-forest.get(b[0]).get(b[1]);
        });
        //按顺序砍树
        int ret=0;
        int bx=0,by=0;
        int step;
        for (int[] t:trees) {
            int x=t[0];
            int y=t[1];
            step=bfs(forest,bx,by,x,y);
            ret+=step;
            if(step==-1) return -1;
            bx=x;
            by=y;
        }
        return ret;
    }
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public  int bfs(List<List<Integer>> f,int bx,int by,int x,int y) {
        if(bx==x && by==y) return 0;
        int step=0;
        Queue<int[]> q=new LinkedList<>();
        boolean[][] vis=new boolean[m][n];
        q.add(new int[]{bx,by});
        vis[bx][by]=true;
        while(!q.isEmpty()){
            step++;
            int sz=q.size();
            for (int i = 0; i < sz; i++) {
                int[] t=q.poll();
                int a=t[0],b=t[1];
                for (int j = 0; j <4 ; j++) {
                    int x1=dx[j]+a;
                    int y1=dy[j]+b;
                    if(x1>=0 && x1<m && y1>=0 && y1<n && !vis[x1][y1] && f.get(x1).get(y1)!=0){

                        q.add(new int[]{x1,y1});
                        vis[x1][y1]=true;
                        if(x1==x && y1==y) return step;
                    }
                }
            }
        }
        return -1;
    }
}
